{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Dynamics"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "In this notebook we present some of the dynamic algorithms in NetworKit to analyze various properties of a (dynamic) graph.\n",
    "See the [networkit.dynamics](https://networkit.github.io/dev-docs/python_api/dynamics.html) module for a more detailed description of the algorithms used here. Dynamic algorithms can compute the result for a modified graph directly from the previous result, without the need to re-run the entire algorithm.\n",
    "\n",
    "Note: The `run()` method does not need to be called in order to adapt the result. Instead, update methods are provided by the `DynAlgorithm` base class."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# As usual, the first step is to import NetworKit.\n",
    "import networkit as nk"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## The Graph and Graph Events"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Note: In order to maintain consistent results, both the graph and the dynamic algorithm need to be adjusted.\n",
    "\n",
    "- The [graph](https://networkit.github.io/dev-docs/python_api/graph.html?highlight=graph#module-networkit.graph) needs to be changed by using the graph manipulation function equivalent to the desired result - like `G.addEdge(...)` or `G.removeEdge(...)`.\n",
    "- The dynamic algorithm needs to be changed, using [graph events](https://networkit.github.io/dev-docs/python_api/dynamics.html?highlight=graphevent#networkit.dynamics.GraphEvent) and calling the functions `update(...)` or `updateBatch(...)`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Initialize graph\n",
    "def initializeGraph():\n",
    "    G = nk.Graph(5, True)\n",
    "    G.addEdge(0, 1, 0.5)\n",
    "    G.addEdge(1, 2, 1.5)\n",
    "    return G\n",
    "\n",
    "\n",
    "# Initialize graph events\n",
    "graphEventEdgeAdd = nk.dynamics.GraphEvent(\n",
    "    nk.dynamics.GraphEventType.EDGE_ADDITION, 2, 4, 2.0\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## DynDijkstra"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The [Dynamic Dijkstra](https://networkit.github.io/dev-docs/python_api/distance.html?highlight=dyndijkstra#networkit.distance.DynDijkstra) algorithm computes the shortest paths to all nodes from a given source node, just like [Dikstra's Algorithm](https://networkit.github.io/dev-docs/python_api/distance.html?highlight=dijkstra#networkit.distance.Dijkstra). The dynamic version is able to handle adding and removing edges in the graph (note that both graph and the dynamic algorithm needs to be updated)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Run Dijsktra algorithm on the initial graph\n",
    "G = initializeGraph()\n",
    "sourceNode = 0\n",
    "dynDijk = nk.distance.DynDijkstra(G, sourceNode)\n",
    "dynDijk.run()\n",
    "print(\"path lengths from source node 0 for initial graph: \", dynDijk.getDistances())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Update the result of the dynamic algorithm\n",
    "G.addEdge(2, 4, 2.0)\n",
    "dynDijk.update(graphEventEdgeAdd)\n",
    "print(\"path lengths from source node 0 after edge addition: \", dynDijk.getDistances())\n",
    "\n",
    "G.removeEdge(2, 4)\n",
    "dynDijk.update(graphEventEdgeAdd)\n",
    "print(\"path lengths from source node 0 after edge removal: \", dynDijk.getDistances())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## DynAPSP"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Similar to the [Dynamic Dijkstra](https://networkit.github.io/dev-docs/python_api/distance.html?highlight=dyndijkstra#networkit.distance.DynDijkstra) algorithm,  there exists a variant of [Dynamic All Pairs Shortest Path](https://networkit.github.io/dev-docs/python_api/distance.html?highlight=dynapsp#networkit.distance.DynAPSP), which computes the shortest path for each node to all other nodes. It can handle graph events of the types `EDGE_ADDITION` and `EDGE_WEIGHT_INCREMENT` with a negative value. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Run APSP algorithm on the initial graph\n",
    "G = initializeGraph()\n",
    "dynAPSP = nk.distance.DynAPSP(G)\n",
    "dynAPSP.run()\n",
    "print(\"path lengths from all nodes for initial graph: \", dynAPSP.getDistances())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "When multiple changes were made to the graph, the `updateBatch` function can be used to update the dynamic algorithm in one step. Depending on the algorithm, this batch update may be more efficient than calling `update` multiple times in sequence."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Batchwise update the result of the dynamic algorithm\n",
    "G.addEdge(1, 3, 1.5)\n",
    "G.addEdge(2, 4, 2.0)\n",
    "G.addEdge(0, 4, 1.5)\n",
    "batch = [\n",
    "    nk.dynamics.GraphEvent(nk.dynamics.GraphEventType.EDGE_ADDITION, 1, 3, 1.5),\n",
    "    nk.dynamics.GraphEvent(nk.dynamics.GraphEventType.EDGE_ADDITION, 2, 4, 2.0),\n",
    "    nk.dynamics.GraphEvent(nk.dynamics.GraphEventType.EDGE_ADDITION, 0, 4, 1.5),\n",
    "]\n",
    "dynAPSP.updateBatch(batch)\n",
    "print(\n",
    "    \"path lengths from all nodes after batch of edge additions: \",\n",
    "    dynAPSP.getDistances(),\n",
    ")\n",
    "\n",
    "# Decreasing edge weights\n",
    "G.increaseWeight(\n",
    "    1, 2, -0.5\n",
    ")  # Weight decrementation is implemented as negative weight increment\n",
    "dynAPSP.update(\n",
    "    nk.dynamics.GraphEvent(nk.dynamics.GraphEventType.EDGE_WEIGHT_INCREMENT, 1, 2, -0.5)\n",
    ")\n",
    "print(\n",
    "    \"path lengths from all nodes after edge weight decrement: \", dynAPSP.getDistances()\n",
    ")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## DynBetweenness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The [Dynamic Betweenness](https://networkit.github.io/dev-docs/python_api/centrality.html?highlight=dynbet#networkit.centrality.DynBetweenness) algorithm computes the _betweenness centrality_ of a graph. It can handle graph events of the types `EDGE_ADDITION` and `EDGE_WEIGHT_INCREMENT` with a negative value and adjusts the result without re-running the entire algorithm again."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Run Betweenness algorithm on the initial graph\n",
    "G = initializeGraph()\n",
    "dynBet = nk.centrality.DynBetweenness(G)\n",
    "dynBet.run()\n",
    "print(\"betweenness scores of initial graph: \", dynBet.scores())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Updating the graph and dynamic algorithm\n",
    "G.increaseWeight(\n",
    "    2, 4, -1.0\n",
    ")  # Weight decrementation is implemented as negative weight increment\n",
    "dynBet.update(\n",
    "    nk.dynamics.GraphEvent(nk.dynamics.GraphEventType.EDGE_WEIGHT_INCREMENT, 2, 4, -1.0)\n",
    ")\n",
    "print(\"betweenness scores of updated graph: \", dynBet.scores())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## DynTopHarmonicCloseness"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The [Dynamic Top Harmonic Closeness](https://networkit.github.io/dev-docs/python_api/centrality.html?highlight=dyn#networkit.centrality.DynTopHarmonicCloseness) algorithm returns the _Harmonic Closeness_ score for the k nodes with highest value. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Run Betweenness algorithm on the initial graph\n",
    "G = initializeGraph()\n",
    "dynHC = nk.centrality.DynTopHarmonicCloseness(G, 3)\n",
    "dynHC.run()\n",
    "print(\"betweenness scores of initial graph: \", dynHC.topkScoresList())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Updating the graph and dynamic algorithm\n",
    "G.addEdge(2, 4)  # Weight decrementation is implemented as negative weight increment\n",
    "dynHC.update(\n",
    "    nk.dynamics.GraphEvent(nk.dynamics.GraphEventType.EDGE_ADDITION, 2, 4, 1.0)\n",
    ")\n",
    "print(\"betweenness scores of updated graph: \", dynHC.topkScoresList())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## DynConnectedComponents"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The [Dynamic Connected Component](https://networkit.github.io/dev-docs/python_api/components.html?highlight=dyn#networkit.components.DynConnectedComponents) algorithm returns the connected components of an undirected graph. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Run Connected Components algorithm on the initial graph\n",
    "G = initializeGraph()\n",
    "dynCC = nk.components.DynConnectedComponents(G)\n",
    "dynCC.run()\n",
    "print(\"connected components of initial graph: \", dynCC.getComponents())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Updating the graph and dynamic algorithm\n",
    "G.addEdge(1, 3)\n",
    "dynCC.update(\n",
    "    nk.dynamics.GraphEvent(nk.dynamics.GraphEventType.EDGE_ADDITION, 1, 3, 1.0)\n",
    ")\n",
    "print(\"connected components of updated graph: \", dynCC.getComponents())"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Other Dynamic Algorithms and Data Structures"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "jp-MarkdownHeadingCollapsed": true,
    "tags": []
   },
   "source": [
    "NetworKit does also include different types of dynamic algorithms and data structures that do not inherit from `DynAlgorithm` which means that they have a different usage: \n",
    "- [DynamicMatrix](https://networkit.github.io/dev-docs/cpp_api/classNetworKit_1_1DynamicMatrix.html?highlight=dynamic#_CPPv4N9NetworKit13DynamicMatrixE)\n",
    "- [DynamicGenerators](https://networkit.github.io/dev-docs/python_api/generators.html?highlight=dynamic#networkit.generators.DynamicDorogovtsevMendesGenerator)\n",
    "- [DynamicNMIDistance](https://networkit.github.io/dev-docs/cpp_api/classNetworKit_1_1DynamicNMIDistance.html?highlight=dynamic#_CPPv4N9NetworKit18DynamicNMIDistanceE)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
